package my.jwds.p102;

import my.jwds.p94.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LevelOrder {

    public static void main(String[] args) {
        LevelOrder obj = new LevelOrder();

        TreeNode treeNode = TreeNode.to_binaryHaveNull(new Integer[] {3,9,20,null,null,15,7});
        System.out.println(obj.levelOrder(treeNode));


    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)return new ArrayList<>();
        LinkedList<TreeNodeAndLevel> queue = new LinkedList<>();
        queue.add(new TreeNodeAndLevel(root));
        List<List<Integer>> res = new ArrayList<>();
        while (!queue.isEmpty()){
            TreeNodeAndLevel t = queue.getFirst();
            queue.removeFirst();
            if (res.size() <= t.level){
                res.add(new ArrayList<>());
            }
            List<Integer> list = res.get(t.level);
            list.add(t.value());
            if (t.left() != null){
                queue.add(t.left());
            }
            if (t.right() != null){
                queue.add(t.right());
            }
        }
        return res;
    }
    class TreeNodeAndLevel{
        TreeNode node;

        int level;

        public TreeNodeAndLevel(TreeNode node) {
            this.node = node;
        }

        public TreeNodeAndLevel(TreeNode node, int level) {
            this.node = node;
            this.level = level;
        }

        public TreeNodeAndLevel right(){
            if (node.right == null){
                return null;
            }
            return new TreeNodeAndLevel(node.right,level+1);
        }


        public TreeNodeAndLevel left(){
            if (node.left == null){
                return null;
            }
            return new TreeNodeAndLevel(node.left,level+1);
        }


        public int value(){
            return node.val;
        }

    }
}